package 基数排序;

import java.io.*;
import java.util.Arrays;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/11/25
 */
// 基数排序，acm练习风格
// 测试链接 : https://www.luogu.com.cn/problem/P1177
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
public class Code01_RadixSort {

    //表示数的进制 可以设置进制，不一定10进制，随你设置
    public static int BASE = 10;
    public static int MAXN = 100001;
    public static int[] arr = new int[MAXN];
    //辅助数组
    public static int[] help = new int[MAXN];
    // cnts[10]：0 1 2 ... 9 每个数的词频，记录在每一轮比较中
    //例如在个位的比较中，arr数组中，个位上的数字存在的个数
    //239 263 939 -> 9:2个，3:1个，没有的就是0
    public static int[] cnts = new int[BASE];
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int)in.nval;
            for(int i = 0; i < n; i++){
                in.nextToken();
                arr[i] = (int)in.nval;
            }
        }
        sort();
        for(int i = 0; i < n-1; i++){
            out.print(arr[i] + " ");
        }
        out.println(arr[n-1]);
        out.flush();
        out.close();
        br.close();
    }

    public static void sort(){
        // 如果会溢出，那么要改用long类型数组来排序
        // 找到数组中的最小值（
        // 防止数组中有负数，对于负数，先都减去最小值，在最后加上最小值）
        int min = arr[0];
        for(int i = 1; i < n; i++){
            min = Math.min(min, arr[i]);
        }
        int max = 0;
        for(int i = 0; i < n; i++){
            // 数组中的每个数字，减去数组中的最小值，就把arr转成了非负数组
            arr[i] -= min;
            // 记录数组中的最大值，通过最大值的位数，来确定比较轮数
            max = Math.max(max, arr[i]);
        }
        // 根据最大值在BASE进制下的位数，决定基数排序做多少轮
        radixSort(bits(max));
        // 数组中所有数都减去了最小值，所以最后不要忘了还原
        for(int i = 0; i < n; i++){
            arr[i] += min;
        }
    }

    //bits 数组中最大值的位数，例4567是4位
    public static int bits(int num){
        int ans = 0;
        while(num > 0){
            num /= BASE;
            ans++;
        }
        return ans;
    }

    // 基数排序核心代码
    // arr内要保证没有负数
    // bits 是arr中最大值在BASE进制下有几位
    public static void radixSort(int bits){
        // 理解的时候可以假设BASE = 10
        for(int offset = 1; bits > 0; offset *= BASE, bits--){
            Arrays.fill(cnts, 0);
            for(int i = 0; i < n; i++){
                // 数字提取某一位的技巧
                cnts[(arr[i] / offset) % BASE]++;
            }
            for(int i = 1; i < BASE; i++){
                cnts[i] = cnts[i] + cnts[i-1];
            }
            for(int i = n-1; i >= 0; i--){
                // 前缀数量分区的技巧
                // 数字提取某一位的技巧
                help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
            }
            for(int i = 0; i < n; i++){
                arr[i] = help[i];
            }
        }
    }
}
